The present disclosure relates to managing sets of data blocks in a storage device. In particular, the present disclosure describes a variable sized reverse map for a storage application. Still more particularly, the present disclosure relates to an efficient and dynamically sized reverse map to handle variable sized data.
Many storage device systems use a dynamic translation table that keeps track of latest mappings from logical to physical media. As and when logical blocks are overwritten, the translation table is updated to point to a new location in the physical media and the old physical media location is reclaimed by the garbage collection process. The garbage collection process works on the contiguous ranges of locations in the physical media, therefore, this process requires the reverse mapping of locations from physical media to logical block address.
With the storage devices supporting data reduction, one physical block can store multiple logical blocks in reduced form. Therefore, there is no one to one relation between the physical block size and the number of logical blocks that can be stored in the storage devices. The size of the reverse map in such systems needs to be dynamic, and preferably depends on the work load. For example if the physical block size is 4096 bytes, with 8× compression the smallest addressable unit becomes of size 512 bytes and simply extending the reverse map to address 512 bytes blocks will have 8× larger memory consumption. The reverse translation table is implemented as paged translation table to constrain the memory consumption, so a larger reverse map is going to consume more space in the physical media. The memory footprint of the system software and the overall efficiency of the garbage collection process are highly dependent on the reverse map implementation.